package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * 滑动谜题
 */
public class Solution3 {
    private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int slidingPuzzle(int[][] board) {
        Queue<String> queue = new LinkedList<>();
        Map<String, Integer> visited = new HashMap<>();
        String initialState = boardToString(board);
        queue.add(initialState);
        visited.put(initialState, 0);
        while (!queue.isEmpty()) {
            String cur = queue.remove();
            List<String> nexts = getNexts(cur);
            for (String next : nexts) {
                if (!visited.containsKey(next)) {
                    queue.add(next);
                    visited.put(next, visited.get(cur) + 1);
                    if (next.equals("123450")) {
                        return visited.get(next);
                    }
                }
            }

        }
        return -1;
    }

    private List<String> getNexts(String curr) {
        int[][] cur = stringToBoard(curr);
        int zero;
        for (zero = 0; zero < 6; zero++) {
            if (cur[zero / 3][zero % 3] == 0) {
                break;
            }
        }
        List<String> res = new ArrayList<>();
        int zx = zero / 3, zy = zero % 3;
        for (int d = 0; d < 4; d++) {
            int nextx = zx + dirs[d][0], nexty = zy + dirs[d][1];
            if (inArea(nextx, nexty)) {
                swap(cur, zx, zy, nextx, nexty);
                res.add(boardToString(cur));
                swap(cur, zx, zy, nextx, nexty);
            }
        }
        return res;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < 2 && y >= 0 && y < 3;
    }

    private void swap(int[][] cur, int zx, int zy, int nextx, int nexty) {
        int curValue = cur[zx][zy];
        cur[zx][zy] = cur[nextx][nexty];
        cur[nextx][nexty] = curValue;

    }

    private int[][] stringToBoard(String s) {
        int[][] board = new int[2][3];
        for (int i = 0; i < 6; i++) {
            board[i / 3][i % 3] = s.charAt(i) - '0';
        }
        return board;
    }

    private String boardToString(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2; i++) {
            for (int j = 0; i < 3; j++) {
                sb.append(board[i][j]);
            }
        }
        return sb.toString();
    }
}
